package com.chj.jz.dp.class06;

public class Code02_InterleavingString {
	public static boolean isInterleave(String ss1, String ss2, String ss3) {
		// write your code here
		char[] s1 = ss1.toCharArray();
		char[] s2 = ss2.toCharArray();
		char[] s3 = ss3.toCharArray();

		int m = s1.length;
		int n = s2.length;
		int z = s3.length;

		if (n + m != z) {
			return false;
		}

		boolean[][] f = new boolean[m + 1][n + 1];

		for (int i = 0; i <= m; i++) {
			for (int j = 0; j <= n; j++) {
				if (i == 0 && j == 0) {
					f[i][j] = true;
					continue;
				}

				f[i][j] = false;
				if (i > 0 && s1[i - 1] == s3[i + j - 1]) {
					f[i][j] |= f[i - 1][j];
				}

				if (j > 0 && s2[j - 1] == s3[i + j - 1]) {
					f[i][j] |= f[i][j - 1];
				}
			}
		}

		return f[m][n];
	}

	public static void main(String[] args) {
		// 输入:
		// "aabcc"
		// "dbbca"
		// "aadbbcbcac"
		{
			String str1 = "aabcc";
			String str2 = "dbbca";
			String str3 = "aadbbcbcac";
			System.out.println(isInterleave(str1, str2, str3));
		}
		{
			String str1 = "";
			String str2 = "";
			String str3 = "1";
			System.out.println(isInterleave(str1, str2, str3));
		}
		{
			String str1 = "aabcc";
			String str2 = "dbbca";
			String str3 = "aadbbbaccc";
			System.out.println(isInterleave(str1, str2, str3));
		}
	}
}
